package qzh;

public class NumMatrix {

    private int[][] matrix;
    private int[][] sum;

    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        int m = matrix.length;
        int n = matrix[0].length;
        //sum数组的第一个值从1开始，这样可以不用考虑边界
        this.sum = new int[m + 1][n + 1];
        /**
         for (int i = 0; i < matrix.length; i++) {
         for (int j = 0; j < matrix.length; j++) {
         System.out.print(matrix[i][j] + " ");
         }
         System.out.println();
         }
         System.out.println("*************");
         */
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                setSum(i, j);
            }
        }
        /*
        System.out.println("*************");
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                System.out.print(sum[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("*************");
         */
    }

    /**
     * 设置sum[row,col]为该区域的所有值求和。
     *
     * @param row
     * @param col
     * @return
     */
    public void setSum(int row, int col) {
        /**
         if (row == 0 && col == 0) {
         sum[0][0] = matrix[0][0];
         return;
         }
         if (row == 0) {
         sum[row][col] = sum[row][col - 1] + matrix[row][col];
         return;
         }
         if (col == 0) {
         sum[row][col] = sum[row - 1][col] + matrix[row][col];
         return;
         }
         */
        // matrix的第一个值仍是从0开始，所以matrix的index需要减1。
        sum[row][col] = sum[row][col - 1] + sum[row - 1][col] - sum[row - 1][col - 1] + matrix[row-1][col-1];
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        /*
        if (row2 == 0 && col2 == 0)
            return sum[0][0];
        if (row2 == 0) {
            return sum[0][col2] - sum[0][col1 - 1];
        }
        if (col2 == 0)
            return sum[row2][0] - sum[row1 - 1][0];

         */
        row1 += 1;
        col1 += 1;
        row2 += 1;
        col2 += 1;
        return sum[row2][col2] - sum[row1 - 1][col2] - sum[row2][col1 - 1] + sum[row1 - 1][col1 - 1];
    }

    public static void main(String[] args) {
        int[][] matrix = {{3, 0, 1, 4, 2}, {5, 6, 3, 2, 1}, {1, 2, 0, 1, 5}, {4, 1, 0, 1, 7}, {1, 0, 3, 0, 5}};

        int region = new NumMatrix(matrix).sumRegion(1, 2, 2, 4);
        System.out.println(region);
    }
}


